Lower Bounds for the Complexity of the Voronoi Diagram of Polygonal Curves under the Discrete Frechet Distance

摘要

We give lower bounds for the combinatorial complexity of the Voronoi diagramof polygonal curves under the discrete Frechet distance. We show that theVoronoi diagram of n curves in R^d with k vertices each, has complexityOmega(n^{dk}) for dimension d=1,2 and Omega(n^{d(k-1)+2}) for d>2.